计算几何

本文大部分图片来自网络,侵权删。

一.向量

1.概念

向量,指具有大小和方向的量,可以形象化地表示为带箭头的线段。

箭头所指代表向量的方向;线段长度代表向量的大小。

2.向量的运算

1.加法

三角形法则:将两个向量首尾相接,连接第一条向量的起点和第二条向量的终点,即为两向量的和。

平行四边形法则:将两个向量平移至公共起点,以向量的两条边作平行四边形,平行四边形的对角线即为两向量的和。

向量加法满足交换律,结合律。

2.减法

三角形法则:将两个向量平移至公共起点,以减向量的终点为起点,被减向量的终点为终点的向量即为两向量的差。

3.数乘

λ\lambda 个相等的非零向量 aa 相加所得的和向量,叫作 λ\lambda 与向量aa的积,记为λa\lambda a

λ>0\lambda > 0时,λa\lambda aaa 同向,当 λ<0\lambda < 0 时,λa\lambda aaa 反向,当 λ=0\lambda=0 时,λa=0\lambda a = 0

向量数乘满足交换律,结合律,分配律。

4.数量积(点积,内积)

ab=a×b×cosθa \cdot b=|a| \times |b| \times \cos \theta

acosθ|a|\cos \theta 叫做 aabb 方向上的投影,
bcosθ|b|\cos \theta 叫做 bbaa 方向上的投影。

  1. ab=baa \cdot b=b \cdot a

  2. (λa)b=a(λb)=λ(ab)(\lambda a ) \cdot b = a \cdot (\lambda b)=\lambda(a \cdot b)

  3. a(b+c)=ab+aca\cdot(b+c)=a\cdot b+a\cdot c

5.向量积(叉积,外积)

ab=a×b×sinθa \land b=|a| \times |b| \times \sin \theta

结果是一个垂直于 aabb 的向量,在平面中可以认为是一个数量。

几何意义是两个向量所构成的平行四边形的有向面积。

  1. ab=(ba)a \land b=-(b \land a)

  2. (λa)b=a(λb)=λ(ab)(\lambda a ) \land b = a \land (\lambda b)=\lambda(a \land b)

  3. a(b+c)=ab+aca \land (b+c)=a \land b+a \land c

需要注意的是,数量积和向量积都不满足结合律。

3.向量的坐标运算

1.平面向量基本定理

在同一平面内,如果两个向量 e1e_1 , e2e_2 不共线,那么对于在同一平面的向量 pp , 存在唯一实数对(λ1,λ2)(\lambda_1,\lambda_2) , 使得 p=λ1e1+λ2e2p= \lambda_1 e_1 + \lambda_2 e_2

在平面上,如果取一对相互垂直的向量作为基底,就可以构建一个平面直角坐标系。记 xx 轴 和 yy 轴的单位向量分别为 ii , jj

对于平面上的任意向量,有 p=ai+bjp=ai+bj , 可以由实数对 (a,b)(a,b) 唯一确定。

2.向量的坐标运算

记两个向量为 a=(x1,y1)a=(x_1,y_1) , b=(x2,y2)b=(x_2,y_2)

1.加法:a+b=(x1+x2,y1+y2)a+b=(x_1+x_2,y_1+y_2)

2.减法:ab=(x1x2,y1y2)a-b=(x_1-x_2,y_1-y_2)

3.数乘:λa=(λx1,λy1)\lambda a=(\lambda x1,\lambda y_1)

4.数量积:ab=x1y1+x2y2a \cdot b=x_1y_1+x_2y_2

5.向量积:ab=x1y2x2y1a \land b=x_1y_2-x_2y_1

4.应用

1.判断两向量的位置关系

1.平行:ab=0a \land b=0

2.垂直:ab=0a \cdot b=0

2.逆时针旋转

θ\theta 为向量与 xx 轴的夹角,α\alpha 为旋转的角度,dd 为向量模长。

首先有:

sinθ=y1d , cosθ=x1d\sin \theta=\frac{y_1}{d}~,~\cos \theta=\frac{x_1}{d}

sin(θ+α)=y2d , cos(θ+α)=x2d\sin (\theta+\alpha)=\frac{y_2}{d}~,~\cos (\theta+\alpha)=\frac{x_2}{d}

用和角公式展开:

sin(θ+α)=sinθcosα+cosθsinα=y1dcosα+x1dsinα\sin (\theta+\alpha)=\sin \theta \cos \alpha + \cos \theta \sin \alpha=\frac{y_1}{d}\cos \alpha +\frac{x_1}{d}\sin \alpha

y2d=y1dcosα+x1dsinα\Rightarrow \frac{y_2}{d}=\frac{y_1}{d}\cos \alpha + \frac{x_1}{d}\sin \alpha

y2=y1cosα+x1sinα\Rightarrow y_2=y_1\cos \alpha + x_1\sin \alpha

cos(θ+α)=cosθcosαsinθsinα=x1dcosαy1dsinα\cos (\theta+\alpha)=\cos \theta \cos \alpha - \sin \theta \sin \alpha=\frac{x_1}{d}\cos \alpha -\frac{y_1}{d}\sin \alpha

x2d=x1dcosαy1dsinα\Rightarrow \frac{x_2}{d}=\frac{x_1}{d}\cos \alpha - \frac{y_1}{d}\sin \alpha

x2=x1cosαy1sinα\Rightarrow x_2=x_1\cos \alpha - y_1\sin \alpha

所以旋转后的向量为 (x1cosαy1sinα,y1cosα+x1sinα)(x_1\cos \alpha - y_1\sin \alpha,y_1\cos \alpha + x_1\sin \alpha)

3.求直线交点

4.判断点是否在线段上

首先 , xp=px,xq=qx\overrightarrow{xp}=p-x ,\overrightarrow{xq}=q-x

如果 xp\overrightarrow{xp}xq\overrightarrow{xq} 的叉积不为 0 (图一) 说明 xp\overrightarrow{xp}xq\overrightarrow{xq} 不共线,xx 一定不在线段上。

不然则计算它们的点积,如果 xp\overrightarrow{xp}xq\overrightarrow{xq} 的点积为正数,说明 xp\overrightarrow{xp}xq\overrightarrow{xq} 同向(如图三)。

所以点向线段端点的两向量的叉积为0,点积为负数,那么点在线段上。

5.模板

struct Vector {
    double x , y;

    Vector operator + ( const Vector &o ) const { //加法
        return { x + o.x , y + o.y }; 
    }
    Vector operator - ( const Vector &o ) const { //减法
        return { x - o.x , y - o.y };
    }
    Vector operator * ( const double &o ) const { //数乘
        return { x * o , y * o };
    }
	double operator * ( const Vector &a ) const { //内积
        return x * a.x + y * a.y;
    }
    double operator ^ ( const Vector &a ) const { //叉积
        return x * a.y - y * a.x;
    }
	
    double len( const Vector &a ) const { //模长
        return sqrt( a.x * a.x + a.y * a.y );
    }
    double theta( const Vector &a ) const { //极角
        return atan( a.y / a.x );
    }
    double Rad( const Vector &a , const Vector &b ) const { //夹角
        return acos( a * b / ( len( a ) * len( b ) ) );
    }

    Vector Rotate( const Vector &a , double rad ) const { //逆时针旋转
        return { a.x * cos( rad ) - a.y * sin( rad ) , a.x * sin( rad ) + a.y * cos( rad ) }; 
    }
    Vector Intersection( const Vector &a , const Vector &b , const Vector &c , const Vector &d ) const { //直线a,c交点(b,d)为斜率
        Vector u = a - c;
        double t = ( d ^ u ) / ( b ^ d );
        return a + b * t;
    }
    bool Online( const Vector &p , const Vector &q ) const { //求点是否在线段上
        return equal( ( p - Point{ x , y } ) ^ ( q - Vector{ x , y } ) , 0 ) && ( ( p - Vector{ x , y } ) * ( q - Vector{ x , y } ) ) < eps;
    }
}dex , alpha;

6.例题

1.[SHOI2015]激光发生器